package Hot100;

public class productExceptSelf {
    public static void main(String[] args) {
        int nums[] = {-1,1,0,-3,3};
        int[] answer = productExceptSelf(nums);
        for (int i = 0; i < answer.length; i++) {
            System.out.println(answer[i]);
        }
    }
    public static int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int has_zero = 0;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 0){
                has_zero = 1;
                index = i;
                break;
            }
        }
        if(has_zero == 1){
            int ans = 1;
            for (int i = 0; i < nums.length; i++) {
                if(i != index){
                    ans = ans * nums[i];
                    answer[i] = 0;
                }
            }
            answer[index] = ans;
        }
        else {
            int[] left = new int[nums.length];
            left[0] = 1;
            int[] right = new int[nums.length];
            right[nums.length - 1] = 1;
            for (int i = 1; i < nums.length; i++) {
                left[i] = left[i-1] * nums[i - 1];
            }
            for (int i = nums.length - 2; i >= 0 ; i--) {
                right[i] = right[i + 1] * nums[i + 1];
            }

            for (int i = 0; i < nums.length; i++) {
                answer[i] = left[i] * right[i];
            }
        }
        return answer;
    }
}
